import java.util.*;

/**
 * Created by zhourh on 2018/9/11.
 */
public class Converter {

    public static TreeNode convertArray2TreeNode(Integer[] array) {
        if (array == null || array.length == 0) {
            return null;
        }

        int offset = 0;
        TreeNode root = new TreeNode(array[offset++]);
        Queue<TreeNode> queue = new LinkedList<>();
        List<TreeNode> level = new ArrayList<>();
        queue.add(root);

        while (!queue.isEmpty()) {
            // 数组已经用尽，返回根节点
            if (offset >= array.length) {
                return root;
            }

            // 记录下一层
            level.clear();
            while (!queue.isEmpty()) {
                if (offset >= array.length) {
                    return root;
                }

                TreeNode parentNode = queue.remove();

                if (array[offset] != null) {
                    parentNode.left = new TreeNode(array[offset]);
                    level.add(parentNode.left);
                }
                offset++;
                if (offset >= array.length) {
                    return root;
                }

                if (array[offset] != null) {
                    parentNode.right = new TreeNode(array[offset]);
                    level.add(parentNode.right);
                }
                offset++;
                if (offset >= array.length) {
                    return root;
                }
            }

            for (TreeNode treeNode : level) {
                if (treeNode != null) {
                    queue.add(treeNode);
                }
            }

        }

        return root;
    }
}
